package com.xufx.algorithm.string;

import java.util.HashSet;
import java.util.Set;

/**
 * leetcode 3. Longest substring without repeating character
 * @link https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
 * describe: Given a string s, find the length of the longest substring without repeating characters.
 *
 * example:
 *  Input: s = "abcabcbb"
 *  Output: 3
 *  Explanation: The answer is "abc", with the length of 3.
 *
 * NOTICE:
 *  1.判断唯一性问题（不重复），想是不是要用Set这种数据结构
 *  2.滑动窗口，滑动的关键是right还能回来
 */
public class Leetcode3LongestSubstringWithoutRepeatingCharacters {

    public static void main(String[] args) {
        String s = "abcabcabcbb";
        int res = lengthOfLongestSubstring(s);
        System.out.println(res);
    }

    private static int lengthOfLongestSubstring(String s) {
        // 利用set 容器工具
        char[] ss = s.toCharArray();
        int len = ss.length;
        // 处理一些特殊情况
        if(len <= 1){
            return len;
        }
        int right = 0;
        int left  = 0;
        int res   = 0;
        Set<Character> set = new HashSet<>();
        while(right < len){
            if(!set.add(ss[right])){
                res = Math.max(res, set.size());
                set.clear();
                left++;
                right = left;
                continue;
            }
            right++;
            if(right == len){
                res = Math.max(res, set.size());
            }
        }
        return res;
    }


}
